ebab7d0da53c51438720d60c6e2e467c - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Matrix geometric method</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Matrix geometric method</span></span>

</h1>

</header>

<p>In <a href="Probability_theory" title="Probability theory">probability theory</a>, the <b>matrix geometric method</b> is a method for the analysis of <a href="Quasi-birth%E2%80%93death_process" title="Quasi-birth–death process">quasi-birth–death processes</a>, <a href="Continuous-time_Markov_chain" title="Continuous-time Markov chain">continuous-time Markov chain</a> whose <a href="Transition_rate_matrices" class="mw-redirect" title="Transition rate matrices">transition rate matrices</a> with a repetitive block structure.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> The method was developed "largely by <a href="Marcel_F._Neuts" title="Marcel F. Neuts">Marcel F. Neuts</a> and his students starting around 1975."<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Method_description">Method description</h2></div>

<p>The method requires a transition rate matrix with <a href="Tridiagonal_matrix" title="Tridiagonal matrix">tridiagonal</a> block structure as follows

</p>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}}</annotation>

</semantics>

</math></span><img src="./85388d0abb062217a7614ba1b877db1cb0270416.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.838ex; width:45.502ex; height:20.843ex;" alt="{\displaystyle Q={\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}&A_{2}\\&A_{0}&A_{1}&A_{2}\\&&A_{0}&A_{1}&A_{2}\\&&&A_{0}&A_{1}&A_{2}\\&&&&\ddots &\ddots &\ddots \end{pmatrix}}}" loading="lazy"></span></dd></dl></dd></dl>

<p>where each of <i>B</i><sub>00</sub>, <i>B</i><sub>01</sub>, <i>B</i><sub>10</sub>, <i>A</i><sub>0</sub>, <i>A</i><sub>1</sub> and <i>A</i><sub>2</sub> are matrices. To compute the stationary distribution <i>π</i> writing <i>π</i> <i>Q</i> = 0 the <a href="Balance_equation" title="Balance equation">balance equations</a> are considered for sub-vectors <i>π</i><sub><i>i</i></sub>

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}\pi _{0}B_{00}+\pi _{1}B_{10}&=0\\\pi _{0}B_{01}+\pi _{1}A_{1}+\pi _{2}A_{0}&=0\\\pi _{1}A_{2}+\pi _{2}A_{1}+\pi _{3}A_{0}&=0\\&\vdots \\\pi _{i-1}A_{2}+\pi _{i}A_{1}+\pi _{i+1}A_{0}&=0\\&\vdots \\\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./692d81dd42fe80ce4c9e5dc516f441998103ac03.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -9.505ex; width:29.66ex; height:20.176ex;" alt="{\displaystyle {\begin{aligned}\pi _{0}B_{00}+\pi _{1}B_{10}&=0\\\pi _{0}B_{01}+\pi _{1}A_{1}+\pi _{2}A_{0}&=0\\\pi _{1}A_{2}+\pi _{2}A_{1}+\pi _{3}A_{0}&=0\\&\vdots \\\pi _{i-1}A_{2}+\pi _{i}A_{1}+\pi _{i+1}A_{0}&=0\\&\vdots \\\end{aligned}}}" loading="lazy"></span></dd></dl></dd></dl>

<p>Observe that the relationship

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \pi _{i}=\pi _{1}R^{i-1}}</annotation>

</semantics>

</math></span><img src="./9638a4bb20c5f9d15419b31802bef186f371ebe2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:12.267ex; height:3.009ex;" alt="{\displaystyle \pi _{i}=\pi _{1}R^{i-1}}" loading="lazy"></span></dd></dl></dd></dl>

<p>holds where <i>R</i> is the Neut's rate matrix,<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> which can be computed numerically. Using this we write

</p>

<mtr>

<mtd>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

<mrow>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

</mtable>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}{\begin{pmatrix}\pi _{0}&\pi _{1}\end{pmatrix}}{\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}+RA_{0}\end{pmatrix}}={\begin{pmatrix}0&0\end{pmatrix}}\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./d238e259368604841c56889f44a3927ccf50a5b9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -2.505ex; width:41.035ex; height:6.176ex;" alt="{\displaystyle {\begin{aligned}{\begin{pmatrix}\pi _{0}&\pi _{1}\end{pmatrix}}{\begin{pmatrix}B_{00}&B_{01}\\B_{10}&A_{1}+RA_{0}\end{pmatrix}}={\begin{pmatrix}0&0\end{pmatrix}}\end{aligned}}}" loading="lazy"></span></dd></dl></dd></dl>

<p>which can be solve to find <i>π</i><sub>0</sub> and <i>π</i><sub>1</sub> and therefore iteratively all the <i>π</i><sub><i>i</i></sub>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Computation_of_R">Computation of <i>R</i></h2></div>

<p>The matrix <i>R</i> can be computed using <a href="Cyclic_reduction" title="Cyclic reduction">cyclic reduction</a><sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> or logarithmic reduction.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup><sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="Matrix_analytic_method">Matrix analytic method</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hatnote{font-style:italic}.mw-parser-output div.hatnote{padding-left:1.6em;margin-bottom:0.5em}.mw-parser-output .hatnote i{font-style:normal}.mw-parser-output .hatnote+link+.hatnote{margin-top:-0.5em}@media print{body.ns-0 .mw-parser-output .hatnote{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div role="note" class="hatnote navigation-not-searchable">Main article: <a href="Matrix_analytic_method" title="Matrix analytic method">Matrix analytic method</a></div>

<p>The matrix analytic method is a more complicated version of the matrix geometric solution method used to analyse models with block <a href="M/G/1_queue" title="M/G/1 queue">M/G/1</a> matrices.<sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup> Such models are harder because no relationship like <i>π</i><sub><i>i</i></sub> = <i>π</i><sub>1</sub> R<sup><i>i</i> – 1</sup> used above holds.<sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup>

</p>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="http://www.sti.uniurb.it/events/sfm07pe/slides/Stewart_2.pdf">Performance Modelling and Markov Chains (part 2)</a> by William J. Stewart at <i>7th International School on Formal Methods for the Design of Computer, Communication and Software Systems: Performance Evaluation</i></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHarrisonPatel1992" class="citation book cs1"><a href="Peter_G._Harrison" title="Peter G. Harrison">Harrison, Peter G.</a>; Patel, Naresh M. (1992). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/performancemodel0000harr/page/317"><i>Performance Modelling of Communication Networks and Computer Architectures</i></a></span>. Addison-Wesley. pp. <a rel="nofollow" class="external text" href="https://archive.org/details/performancemodel0000harr/page/317">317–322</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-54419-9</bdi>.</cite></span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text"><cite id="CITEREFAsmussen2003" class="citation book cs1">Asmussen, S. R. (2003). "Random Walks". <i>Applied Probability and Queues</i>. Stochastic Modelling and Applied Probability. Vol. 51. pp. <span class="nowrap">220–</span>243. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2F0-387-21525-5_8">10.1007/0-387-21525-5_8</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-387-00211-8</bdi>.</cite></span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text"><cite id="CITEREFRamaswami1990" class="citation journal cs1">Ramaswami, V. (1990). "A duality theorem for the matrix paradigms in queueing theory". <i>Communications in Statistics. Stochastic Models</i>. <b>6</b>: <span class="nowrap">151–</span>161. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F15326349908807141">10.1080/15326349908807141</a>.</cite></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><b><a href="#cite_ref-4">^</a></b></span> <span class="reference-text"><cite id="CITEREFBiniMeini1996" class="citation journal cs1">Bini, D.; <a href="Beatrice_Meini" title="Beatrice Meini">Meini, B.</a> (1996). "On the Solution of a Nonlinear Matrix Equation Arising in Queueing Problems". <i>SIAM Journal on Matrix Analysis and Applications</i>. <b>17</b> (4): 906. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1137%2FS0895479895284804">10.1137/S0895479895284804</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite id="CITEREFLatoucheRamaswami1993" class="citation journal cs1">Latouche, Guy; Ramaswami, V. (1993). "A Logarithmic Reduction Algorithm for Quasi-Birth-Death Processes". <i>Journal of Applied Probability</i>. <b>30</b> (3). Applied Probability Trust: <span class="nowrap">650–</span>674. <a href="JSTOR_(identifier)" class="mw-redirect" title="JSTOR (identifier)">JSTOR</a> <a rel="nofollow" class="external text" href="https://www.jstor.org/stable/3214773">3214773</a>.</cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite id="CITEREFPérezVan_Houdt2011" class="citation journal cs1">Pérez, J. F.; Van Houdt, B. (2011). <a rel="nofollow" class="external text" href="http://www.doc.ic.ac.uk/~jperezbe/data/PerezVanHoudt_PEVA_2011.pdf">"Quasi-birth-and-death processes with restricted transitions and its applications"</a> <span class="cs1-format">(PDF)</span>. <i><a href="Performance_Evaluation" title="Performance Evaluation">Performance Evaluation</a></i>. <b>68</b> (2): 126. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1016%2Fj.peva.2010.04.003">10.1016/j.peva.2010.04.003</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10067%2F859850151162165141">10067/859850151162165141</a></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite id="CITEREFAlfaRamaswami2011" class="citation book cs1">Alfa, A. S.; Ramaswami, V. (2011). "Matrix Analytic Method: Overview and History". <i>Wiley Encyclopedia of Operations Research and Management Science</i>. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1002%2F9780470400531.eorms0631">10.1002/9780470400531.eorms0631</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>9780470400531</bdi>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text"><cite id="CITEREFBolchGreinerde_MeerTrivedi2006" class="citation book cs1">Bolch, Gunter; Greiner, Stefan; de Meer, Hermann; <a href="Kishor_S._Trivedi" title="Kishor S. Trivedi">Trivedi, Kishor Shridharbhai</a> (2006). <i>Queueing Networks and Markov Chains: Modeling and Performance Evaluation with Computer Science Applications</i> (2 ed.). John Wiley & Sons, Inc. p. 259. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0471565253</bdi>.</cite></span>

</li>

</ol></div></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Queueing_theory265" style="padding:3px"><table class="nowraplinks mw-collapsible uncollapsed navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Queueing_theory265" style="font-size:114%;margin:0 4em"><a href="Queueing_theory" title="Queueing theory">Queueing theory</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%">Single queueing nodes</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="D/M/1_queue" title="D/M/1 queue">D/M/1 queue</a></li>

<li><a href="M/D/1_queue" title="M/D/1 queue">M/D/1 queue</a></li>

<li><a href="M/D/c_queue" title="M/D/c queue">M/D/c queue</a></li>

<li><a href="M/M/1_queue" title="M/M/1 queue">M/M/1 queue</a>

<ul><li><a href="Burke's_theorem" title="Burke's theorem">Burke's theorem</a></li></ul></li>

<li><a href="M/M/c_queue" title="M/M/c queue">M/M/c queue</a></li>

<li><a href="M/M/%E2%88%9E_queue" title="M/M/∞ queue">M/M/∞ queue</a></li>

<li><a href="M/G/1_queue" title="M/G/1 queue">M/G/1 queue</a>

<ul><li><a href="Pollaczek%E2%80%93Khinchine_formula" title="Pollaczek–Khinchine formula">Pollaczek–Khinchine formula</a></li>

<li><a href="Matrix_analytic_method" title="Matrix analytic method">Matrix analytic method</a></li></ul></li>

<li><a href="M/G/k_queue" title="M/G/k queue">M/G/k queue</a></li>

<li><a href="G/M/1_queue" title="G/M/1 queue">G/M/1 queue</a></li>

<li><a href="G/G/1_queue" title="G/G/1 queue">G/G/1 queue</a>

<ul><li><a href="Kingman's_formula" title="Kingman's formula">Kingman's formula</a></li>

<li><a href="Lindley_equation" title="Lindley equation">Lindley equation</a></li></ul></li>

<li><a href="Fork%E2%80%93join_queue" title="Fork–join queue">Fork–join queue</a></li>

<li><a href="Bulk_queue" title="Bulk queue">Bulk queue</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Arrival processes</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Poisson_point_process" title="Poisson point process">Poisson point process</a></li>

<li><a href="Markovian_arrival_process" title="Markovian arrival process">Markovian arrival process</a></li>

<li><a href="Rational_arrival_process" title="Rational arrival process">Rational arrival process</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Queueing networks</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Jackson_network" title="Jackson network">Jackson network</a>

<ul><li><a href="Traffic_equations" title="Traffic equations">Traffic equations</a></li></ul></li>

<li><a href="Gordon%E2%80%93Newell_theorem" title="Gordon–Newell theorem">Gordon–Newell theorem</a>

<ul><li><a href="Mean_value_analysis" title="Mean value analysis">Mean value analysis</a></li>

<li><a href="Buzen's_algorithm" title="Buzen's algorithm">Buzen's algorithm</a></li></ul></li>

<li><a href="Kelly_network" title="Kelly network">Kelly network</a></li>

<li><a href="G-network" title="G-network">G-network</a></li>

<li><a href="BCMP_network" title="BCMP network">BCMP network</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Service policies</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Processor_sharing" title="Processor sharing">Processor sharing</a></li>

<li><a href="Round-robin_scheduling" title="Round-robin scheduling">Round-robin</a></li>

<li><a href="Shortest_job_next" title="Shortest job next">Shortest job next</a></li>

<li><a href="Shortest_remaining_time" title="Shortest remaining time">Shortest remaining time</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Key concepts</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Continuous-time_Markov_chain" title="Continuous-time Markov chain">Continuous-time Markov chain</a></li>

<li><a href="Kendall's_notation" title="Kendall's notation">Kendall's notation</a></li>

<li><a href="Little's_law" title="Little's law">Little's law</a></li>

<li><a href="Product-form_solution" title="Product-form solution">Product-form solution</a>

<ul><li><a href="Balance_equation" title="Balance equation">Balance equation</a></li>

<li><a href="Quasireversibility" title="Quasireversibility">Quasireversibility</a></li>

<li><a href="Flow-equivalent_server_method" title="Flow-equivalent server method">Flow-equivalent server method</a></li></ul></li>

<li><a href="Arrival_theorem" title="Arrival theorem">Arrival theorem</a></li>

<li><a href="Decomposition_method_(queueing_theory)" title="Decomposition method (queueing theory)">Decomposition method</a></li>

<li><a href="Bene%C5%A1_method" title="Beneš method">Beneš method</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Limit theorems</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fluid_limit" title="Fluid limit">Fluid limit</a></li>

<li><a href="Mean-field_theory" title="Mean-field theory">Mean-field theory</a></li>

<li><a href="Heavy_traffic_approximation" title="Heavy traffic approximation">Heavy traffic approximation</a>

<ul><li><a href="Reflected_Brownian_motion" title="Reflected Brownian motion">Reflected Brownian motion</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Extensions</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Fluid_queue" title="Fluid queue">Fluid queue</a></li>

<li><a href="Layered_queueing_network" title="Layered queueing network">Layered queueing network</a></li>

<li><a href="Polling_system" title="Polling system">Polling system</a></li>

<li><a href="Adversarial_queueing_network" title="Adversarial queueing network">Adversarial queueing network</a></li>

<li><a href="Loss_network" title="Loss network">Loss network</a></li>

<li><a href="Retrial_queue" title="Retrial queue">Retrial queue</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Information_system" title="Information system">Information systems</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Data_buffer" title="Data buffer">Data buffer</a></li>

<li><a href="Erlang_(unit)" title="Erlang (unit)">Erlang (unit)</a></li>

<li><a href="Erlang_distribution" title="Erlang distribution">Erlang distribution</a></li>

<li><a href="Flow_control_(data)" title="Flow control (data)">Flow control (data)</a></li>

<li><a href="Message_queue" title="Message queue">Message queue</a></li>

<li><a href="Network_congestion" title="Network congestion">Network congestion</a></li>

<li><a href="Network_scheduler" title="Network scheduler">Network scheduler</a></li>

<li><a href="Pipeline_(software)" title="Pipeline (software)">Pipeline (software)</a></li>

<li><a href="Quality_of_service" title="Quality of service">Quality of service</a></li>

<li><a href="Scheduling_(computing)" title="Scheduling (computing)">Scheduling (computing)</a></li>

<li><a href="Teletraffic_engineering" title="Teletraffic engineering">Teletraffic engineering</a></li></ul>

</div></td></tr><tr><td class="navbox-abovebelow" colspan="2"><div><span class="noviewer" typeof="mw:File"><span title="Category"></span></span> Category</div></td></tr></tbody></table></div>

<p><br>

</p>

/* start https://en.wikipedia.org/ */

.mw-parser-output .asbox{position:relative;overflow:hidden}.mw-parser-output .asbox table{background:transparent}.mw-parser-output .asbox p{margin:0}.mw-parser-output .asbox p+p{margin-top:0.25em}.mw-parser-output .asbox-body{font-style:italic}.mw-parser-output .asbox-note{font-size:smaller}.mw-parser-output .asbox .navbar{position:absolute;top:-0.75em;right:1em;display:none}.mw-parser-output :not(p):not(.asbox)+style+.asbox,.mw-parser-output :not(p):not(.asbox)+link+.asbox{margin-top:3em}

/* end https://en.wikipedia.org/ */

</style></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-05-10" href="https://en.wikipedia.org/wiki/?title=Matrix_geometric_method&oldid=1223151674">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>